/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //遍历每个节点的左右子树的高度
// class Solution {
//     int deep(TreeNode* root)
//     {
//         if (root == nullptr)
//             return 0;

//         return max(deep(root->left), deep(root->right)) + 1;
//     }
//     void diameterOfBinaryTree(TreeNode* root, int& d)
//     {
//         if (!root)
//             return;

//         int l_deep = deep(root->left);
//         int r_deep = deep(root->right);
//         if (l_deep > r_deep)
//         {
//             d = max(d, l_deep + r_deep);
//             diameterOfBinaryTree(root->left, d);
//         }
//         else
//         {
//             d = max(d, l_deep + r_deep);
//             diameterOfBinaryTree(root->right, d);
//         }
//     }
// public:
//     int diameterOfBinaryTree(TreeNode* root) {
//         int max_d = 0;
//         diameterOfBinaryTree(root, max_d);
//         return max_d;
//     }
// };

//边算树的最大高度，边更新直径
//算数目的最大高度本来就要将每个节点的左右子树的高度求一遍
class Solution {
    int deep(TreeNode* root, int& d)
    {
        if (root == nullptr)
            return 0;
        
        int ld = deep(root->left, d);
        int rd = deep(root->right, d);
        d = max(d, ld + rd);

        return max(ld, rd) + 1;
    }
    
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int max_d = 0;
        deep(root, max_d);
        return max_d;
    }
};